3841. Банкет Доктора Кто

Доктор Кто организовывает банкет и приглашает несколько гостей. Гость счастлив, если он может пообщаться с определенным количеством других гостей. Гость не может общаться сам с собой. Помогите доктору Кто сделать всех гостей счастливыми, если это возможно, организовав общение между гостями.

Вход. Состоит из нескольких тестов, каждый из которых содержится в отдельной строке. Тест состоит из n (n ≤ 10000) натуральных чисел a₁, a₂, … a_n. Каждое число a_i (a_i ≤ 1000, 1 ≤ i ≤ n) означает количество партнеров для общения, которое хотел бы получить гость i.

Выход. Если можно сделать всех гостей счастливыми, то следует сообщение "ok". Если не все гости смогут быть счастливыми, следует вывести сообщение "fail". После каждого сообщения следует выводить пустую строку.

В примере входные данные содержат 4 теста.

Пример входа	Пример выхода
3 3 1 1 4 4 3 3 2 2 2 3 3 1 1 2 2 2 2	fail ok fail ok

РЕШЕНИЕ

куча

Анализ алгоритма

Занесем входные числа одного теста в max-очередь с приоритетами. Пусть партнер v находится на вершине очереди. Тогда поставим ему в собеседники тех, кто желал бы получить наибольшее количество партнеров для общения. Получаем жадный алгоритм установления соответствий для общения. Если всех партнеров можно удовлетворить следуя указанному алгоритму, то выводим ok. Иначе выводим fail.

Пример

В четвертом тесте имеется 4 гостя, каждый желает общаться с двумя другими. Партнеров для общения можно сопоставить следующим образом:

Рассмотрим второй тест. Всего имеется 7 гостей. Для общения человеку, который хочет иметь 4 собеседника, поставим в соответствие тех, кто хочет соответственно иметь 4, 3, 3 и 2 собеседника.

Для общения человеку, который хочет иметь еще 3 собеседника, поставим в соответствие тех, кто хочет соответственно иметь 2, 2 и 2 собеседника.

Третья итерация:

Четвертая (последняя) итерация:

Реализация алгоритма

Объявим max-очередь с приоритетами.

priority_queue<int> pq;

Обработка очереди согласно выше описанному алгоритму.

bool process(priority_queue<int> &q)

{

while(!q.empty())

{

Извлекаем гостя, который хочет иметь v собеседников. Значение v – максимальное в очереди.

int v = q.top(); q.pop();

queue<int> add;

Гостю следует найти в точности v собеседников, совершаем v итераций.

while(v--)

{

Если очередь пуста, то все собеседники найдены не будут, ответ будет fail.

if (q.empty()) return false;

Уменьшим на 1 количество собеседников у следующего гостя. Количество желаемых собеседников для следующего гостя заносим в очередь add.

if (q.top() != 1) add.push(q.top() - 1);

q.pop();

}

Возвращаем собеседников из очереди add в q.

while(!add.empty())

{

q.push(add.front());

add.pop();

}

}

return true;

}

Основная часть программы. Читаем числа одной строки (одного теста). Когда после числа будет прочитан символ '\n', произойдет обработка данных. Если ответ утвердительный, то выводим ok, иначе fail.

while(scanf("%d%c",&n,&c) == 2)

{

pq.push(n);

if (c == '\n')

{

printf(process(pq) ? "ok\n\n" : "fail\n\n");

Чистим очередь для ее использования в следующем тесте.

while(!pq.empty()) pq.pop();

}

}